package 每日一题;

import java.util.*;

public class No554砖墙 {

    /**
     * 你的面前有一堵矩形的、由 n 行砖块组成的砖墙。
     * 这些砖块高度相同（也就是一个单位高）但是宽度不同。每一行砖块的宽度之和应该相等。
     * 你现在要画一条 自顶向下 的、穿过 最少 砖块的垂线。
     * 如果你画的线只是从砖块的边缘经过，就不算穿过这块砖。
     * 你不能沿着墙的两个垂直边缘之一画线，这样显然是没有穿过一块砖的。
     * 给你一个二维数组 wall ，该数组包含这堵墙的相关信息。
     * 其中，wall[i] 是一个代表从左至右每块砖的宽度的数组。
     * 你需要找出怎样画才能使这条线 穿过的砖块数量最少 ，并且返回 穿过的砖块数量 。
     *
     * 示例 1：
     * 输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
     * 输出：2
     * 示例 2：
     * 输入：wall = [[1],[1],[1]]
     * 输出：3
     *  
     * 提示：
     * n == wall.length
     * 1 <= n <= 104
     * 1 <= wall[i].length <= 104
     * 1 <= sum(wall[i].length) <= 2 * 104
     * 对于每一行 i ，sum(wall[i]) 应当是相同的
     * 1 <= wall[i][j] <= 231 - 1
     */

    public int leastBricks(List<List<Integer>> wall) {

        //k:v  k间隙下标 v数量
        Map<Integer,Integer> map=new HashMap<>();
        int wallSum=0;

        for (List<Integer> list : wall) {
            int sum=0;
            for (Integer index : list) {
                sum+=index;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
            wallSum=sum;//不加最后的下标
        }

        map.remove(wallSum);

        int maxCount=0;

        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

            if(entry.getValue()>maxCount){
                maxCount=entry.getValue();
            }

        }

        return wall.size()-maxCount;
    }

    public static void main(String[] args) {
        No554砖墙 n=new No554砖墙();

        List<List<Integer>> lists=new ArrayList<>();
        lists.add(Arrays.asList(1,2,2,1));
        lists.add(Arrays.asList(3,1,2));
        lists.add(Arrays.asList(1,3,2));
        lists.add(Arrays.asList(2,4));
        lists.add(Arrays.asList(3,1,2));
        lists.add(Arrays.asList(1,3,1,1));

        int result = n.leastBricks(lists);
        System.out.println(result);

    }

}
